package com.dyb.demo.algorithm.array;

import java.util.Random;

/**
 * 快速排序
 * @author dyb
 * @date 2021/6/13
 */
public class QuickSort {

    /**
     * {34, 94, 57, 85, 47, 26, 53, 15}
     * key = 34， {15, 26，34, 85, 47, 57, 53, 94}
     * 取一个基准数key，移动指针从两侧和key作比较，把小于key的放在数组左侧，大于key的放在数组右侧
     * 这样下一次只需要对key左右两侧排序，把数组拆为两部分再分别排序 {15, 26} 34 {85, 47, 57, 53, 94}
     * @param args
     */
    public static void main(String[] args) {
        int[] array = {34, 94, 57, 85, 47, 26, 53, 15};

        quickSort(array, 0, array.length - 1);

        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            System.out.print("\t");
        }

    }

    private static void quickSort(int[] array, int leftIndex, int rightIndex) {

        if (leftIndex >= rightIndex) return;

        int left = leftIndex, right = rightIndex;

        // 取最左边数为基准key
        int key = array[left];

        while(left < right) {
            // 从右侧寻找小于key的值
            while(left < right && key <= array[right]) {
                right--;
            }
            array[left] = array[right];

            // 从左侧寻找大于key的值
            while(left < right && key >= array[left]) {
                left++;
            }
            array[right] = array[left];
        }

        // 这时 left == right
        array[left] = key;

        // 易错点，leftIndex、rightIndex作为递归终结条件
        // 对key左侧排序
        quickSort(array, leftIndex, left - 1);
        // 对key右侧排序
        quickSort(array, right + 1, rightIndex);
    }


}
